/*
	@ 后面可以进行打印输出，查看first集，follow集，action表，goto表，状态转化图 等等
	@ first、follow、action、goto、状态转化图均动态生成
	@ 输入：token.txt grammar.txt
	@ 文法开始符号为 P
 	@ @ 表示空字符串
 	@ 运行-命令行
 	g++ 试验二.cpp
 	a
*/

#include<iostream>
#include<fstream>
#include<string>
#include<vector>
#include<queue>
#include<unordered_set>
#include<unordered_map>
#include<algorithm>
#include<stack>
#include"semantic.h"

using namespace std;
Symbol kong;// 空字符串
/*
	@功能 求出items所有非内核项，并且为其赋值
	@参数 exps:所有生成式 items:内核项已经填好的项集
	@返回值 空
*/

void closeure(vector<ProductionExpression> &exps,Items &items){
	// 求出非内核项
	queue<Item> q; //访问队列
	unordered_set<string> visited; // 被访问过非终结符集合
	for(int i = 0;i<items.kernelItems.size();++i){
		q.push(items.kernelItems[i]);
	}
	while(!q.empty()){
		Item item = q.front();
		q.pop();
		int wrapperidx = item.wrapperidx;
		int expidx = item.expidx;
		int pos = item.pos;

		if (pos==exps[wrapperidx].rights[expidx].size()){
			// 点已经移动到了最后一个
			continue;
		}
		string name = exps[wrapperidx].rights[expidx][pos].name;
		if (visited.find(name)!=visited.end()){
			// 已经找了
			continue;
		}
		if (!isupper(name[0])){
			// 不是非终结符
			continue;
		}
		visited.insert(name);
		for(int j = 0; j < exps.size();++j){
			if (exps[j].left.name == name){
				for (int k = 0;k<exps[j].rights.size();++k){
					Item itemTmp(j,k,0);
					if (exps[j].rights[k][0].name=="@"){
						itemTmp.pos=1;
						items.kernelItems.push_back(itemTmp);  // 作为内核项
					}
					else{
						items.nonKernelItems.push_back(itemTmp);
					}
					q.push(itemTmp);
				}
				break;
			}
		}
	}
}

/*
	@功能 求出项集所有下一项（点的下一个符号）名称，放到names里面
	@参数 exps 所有生成式 items 所求项集 names 为符号名称
	@返回值 空
*/

void getAllNames(vector<ProductionExpression> &exps,Items &items,vector<string> &names){
	for (int i = 0;i<items.kernelItems.size();++i){
		int wrapperidx = items.kernelItems[i].wrapperidx;
		int expidx = items.kernelItems[i].expidx;
		int pos = items.kernelItems[i].pos;
		if (exps[wrapperidx].rights[expidx].size()==pos){// 点移动到了最后
			continue;
		}
		bool flag = false;
		for(int j = 0;j<names.size();++j){
			if (names[j] == exps[wrapperidx].rights[expidx][pos].name){
				flag = true;
				break;
			}
		}
		if (!flag){
			names.push_back(exps[wrapperidx].rights[expidx][pos].name);
		}
	}
	for (int i = 0;i<items.nonKernelItems.size();++i){
		int wrapperidx = items.nonKernelItems[i].wrapperidx;
		int expidx = items.nonKernelItems[i].expidx;
		int pos = items.nonKernelItems[i].pos;
		if (exps[wrapperidx].rights[expidx].size()==pos){// 点移动到了最后
			continue;
		}
		bool flag = false;
		for(int j = 0;j<names.size();++j){
			if (names[j] == exps[wrapperidx].rights[expidx][pos].name){
				flag = true;
				break;
			}
		}
		if (!flag){
			names.push_back(exps[wrapperidx].rights[expidx][pos].name);
		}
	}
}

/*
	@功能 求出项集items接收到name符号进入的下一个项集
	@参数 exps 所有生成式 items 源项集 name 接收到的符号名称
	@返回值 下一个项集，已经包含所有内核项
*/
Items GoTo(vector<ProductionExpression> &exps,Items &items,string name){
	Items res;
	// vector<Item> kernelItems;
	for (int i = 0;i<items.kernelItems.size();++i){
		int wrapperidx = items.kernelItems[i].wrapperidx;
		int expidx = items.kernelItems[i].expidx;
		int pos = items.kernelItems[i].pos;
		if (exps[wrapperidx].rights[expidx].size()==pos){// 点移动到了最后
			continue;
		}
		if (exps[wrapperidx].rights[expidx][pos].name == name){
			res.kernelItems.push_back(Item(wrapperidx,expidx,pos+1)); // 向右移动了一个单位
		}
	}
	for (int i = 0;i<items.nonKernelItems.size();++i){
		int wrapperidx = items.nonKernelItems[i].wrapperidx;
		int expidx = items.nonKernelItems[i].expidx;
		int pos = items.nonKernelItems[i].pos;
		if (exps[wrapperidx].rights[expidx][pos].name == name){
			res.kernelItems.push_back(Item(wrapperidx,expidx,pos+1)); // 向右移动了一个单位
		}
	}
	return res;
}

/*
	@功能 求出first集合，放到first中
	@参数 exps 所有生成式 first集合(引用类型)
	@返回值 空
*/
void First(vector<ProductionExpression> &exps,unordered_map<Symbol,vector<Symbol>, myHashFuc > &first){
	for (int i = 0;i<exps.size();++i){// 终结符first初始化
		for(int j = 0;j<exps[i].rights.size();++j){
			for (int k = 0;k<exps[i].rights[j].size();++k){
				Symbol sym = exps[i].rights[j][k];
				if (sym.type==0&&find(first[sym].begin(),first[sym].end(),sym)==first[sym].end()){
					first[sym].push_back(sym);
				}
			}
		}
	}

	while(true){ // 遍历产生式
		bool flag = true;// 产生标记
		for(int i = 0;i<exps.size();++i){
			Symbol symLeft = exps[i].left;
			for (int j = 0;j<exps[i].rights.size();++j){
				bool kongFlag = true;
				for (int k = 0;k<exps[i].rights[j].size();++k){
					Symbol symRight = exps[i].rights[j][k];
					if (symRight.type == 0&&find(first[symLeft].begin(),first[symLeft].end(),symRight)==first[symLeft].end()&&kong!=symRight){
						//终结符
						first[symLeft].push_back(symRight);
						flag = false;
						kongFlag = false;
						break;
					}
					else if (kong!=symRight){
						for (int l = 0;l<first[symRight].size();++l){
							if (find(first[symLeft].begin(),first[symLeft].end(),first[symRight][l])==first[symLeft].end()&&kong!=first[symRight][l]&&kong!=first[symRight][l]){
								first[symLeft].push_back(first[symRight][l]);
								flag = false;
							}
						}
						if (find(first[symRight].begin(),first[symRight].end(),kong)==first[symRight].end()){
							kongFlag = false;
							break;
						}
					}
				}
				if (kongFlag&&find(first[symLeft].begin(),first[symLeft].end(),kong)==first[symLeft].end()){
					first[symLeft].push_back(kong);
					flag = false;
				}
			}
		}
		if (flag) break; // 没有一轮新加入的就算法结束
	}
}
/*
	@功能 求出Follow集 类比first
	@参数 类比first
	@返回值 空
*/
void Follow(vector<ProductionExpression> &exps,
			unordered_map<Symbol,vector<Symbol>, myHashFuc > &first,
			unordered_map<Symbol,vector<Symbol>, myHashFuc > &follow){
	while(true){ // 遍历产生式
		bool flag = true;// 产生标记
		for(int i = 0;i<exps.size();++i){
			Symbol symLeft = exps[i].left;
			for (int j = 0;j<exps[i].rights.size();++j){
				bool kongFlag = true;
				for (int k = exps[i].rights[j].size()-1;k>=0;--k){
					Symbol symRight = exps[i].rights[j][k];
					if (kongFlag){
						for(int l = 0;l<follow[symLeft].size();++l){
							if (find(follow[symRight].begin(),follow[symRight].end(),follow[symLeft][l])!=follow[symRight].end()){
								continue;
							}
							follow[symRight].push_back(follow[symLeft][l]);
							flag = false;
						}
						if (find(first[symRight].begin(),first[symRight].end(),kong)==first[symRight].end()){
							kongFlag = false;
						}
					}
					for (int l = k+1;l<exps[i].rights[j].size();++l){
						Symbol tmp = exps[i].rights[j][l];
						for (int l1 = 0;l1<first[tmp].size();++l1){
							if (kong==first[tmp][l1]){
								continue;
							}
							if (find(follow[symRight].begin(),follow[symRight].end(),first[tmp][l1])!=follow[symRight].end()){
								continue;
							}
							follow[symRight].push_back(first[tmp][l1]);
							flag = false;
						}
						if (find(first[tmp].begin(),first[tmp].end(),kong)==first[tmp].end()){
							break;
						}
					}
				}
			}
		}
		if (flag) break; // 没有一轮新加入的就算法结束
	}
}
/*
	@功能 求出action表和goto表
	@参数 exps 所有生成式 allItems 所有项集(集族) follow表 ACTION GOTO 引用类型直接对其赋值
	@返回值 空
*/
void action_goto(vector<ProductionExpression> &exps,
				 vector<Items> &allItems,
				 unordered_map<Symbol,vector<Symbol>, myHashFuc > &follow,
				 unordered_map<int,unordered_map<Symbol,Act,myHashFuc> > &ACTION,
				 unordered_map<int,unordered_map<Symbol,Act,myHashFuc> > &GOTO){
	for (int i = 0;i<allItems.size();++i){
		for (int j = 0;j<allItems[i].directions.size();++j){
			Symbol sym;
			sym.name = allItems[i].directions[j].name;
			if (!isupper(allItems[i].directions[j].name[0])){
				// cout<<i<<" "<<sym.name<<" "<<allItems[i].directions[j].state<<endl;
				sym.type = 0;
				ACTION[i][sym].type = 0;
				ACTION[i][sym].state = allItems[i].directions[j].state;
			}
			else{
				GOTO[i][sym].state = allItems[i].directions[j].state;
			}
		}
		for(int j = 0;j<allItems[i].kernelItems.size();++j){
			int wrapperidx = allItems[i].kernelItems[j].wrapperidx;
			int expidx = allItems[i].kernelItems[j].expidx;
			int pos = allItems[i].kernelItems[j].pos;
			if (exps[wrapperidx].rights[expidx].size()==pos){ // 点移动到了最后
				//可以规约了
				Symbol left = exps[wrapperidx].left;
				vector<Symbol> reduction = follow[left];
				for (int k = 0;k<reduction.size();++k){
					if (ACTION[i].find(reduction[k])!=ACTION[i].end()){
						int type = ACTION[i][reduction[k]].type;
						if (type==0) {
							cout<<i<<endl;
							cout<<reduction[k].name<<endl;
							cout<<"s-r crash!"<<endl;
							// exit(0);
						}
						else{
							cout<<3<<endl;
							cout<<"r-r crash!"<<endl;
							// exit(0);
							ACTION[i][reduction[k]].type = 1;
							ACTION[i][reduction[k]].state = wrapperidx; // else 如果选择匹配最近if的话 选择移入
							ACTION[i][reduction[k]].expidx = expidx;
						}
					}
					else{
						ACTION[i][reduction[k]].type = 1;
						ACTION[i][reduction[k]].state = wrapperidx; // else 如果选择匹配最近if的话 选择移入
						ACTION[i][reduction[k]].expidx = expidx;
					}
				}
			}
		}
	}
}
// 打印符号表
void printTable(vector<table_item> &table){
	cout<<"########################"<<endl;
	cout<<"name | kind | type | val | addr"<<endl;
	for (int i = 0;i<table.size();++i){
		cout<<table[i].w_name<<" "<<table[i].w_kind<<" "<<table[i].w_type<<" "<<table[i].w_val<<" "<<table[i].w_addr<<endl;
	}
}

/*
	@功能 处理词法分析得到的token序列 打印产生式
	@参数 sym 传来的符号 ......
	@返回值 -1 处理错误 0 成功 1 归约 2 移入
	@语义分析加入table
*/
// -1 处理错误 0 成功 1 归约 2 移入
int Process(Symbol sym,
			vector<ProductionExpression> &exps,
			unordered_map<int,unordered_map<Symbol,Act,myHashFuc> > &ACTION,
			unordered_map<int,unordered_map<Symbol,Act,myHashFuc> > &GOTO,
			vector<table_item> &table,
			stack<Symbol> &symStack,
			stack<int> &stateStack){
	if (ACTION[stateStack.top()].find(sym)==ACTION[stateStack.top()].end()){
		// cout<<sym.name<<endl;
		cout<<sym.name<<" error1"<<endl;
		return -1;
	}
	else if (stateStack.top()==1&&stateStack.size()==2&&sym.name=="$"){ //"01"右边为栈顶
		// 成功识别
		Symbol leftS;
		cout<<sym.name<<" success"<<endl;
		
		cout<<"########################"<<endl;
		semanticAnalysis(0,exps,symStack,table,leftS);
		// printSymbolTable();//打印符号表
		// printSymbolTable();
		printTable(table);
		return 0;
	}
	Act act = ACTION[stateStack.top()][sym];
	if (act.type==0){// 移入
		symStack.push(sym);
		stateStack.push(act.state);
		// cout<<sym.name<<"-shift"<<endl;
		// cout<<stateStack.top()<<endl;
		return 2;
	}
	else{  //规约
		int expressLen = exps[act.state].rights[act.expidx].size();
		if(exps[act.state].rights[act.expidx][0]==kong) expressLen = 0;// 空式子不弹栈\
		// 语义分析
		// 分析动作
		// 首先获取规约式编号
		int eid = 0;
		for(int i = 0;i<act.state;++i){
			eid += exps[i].rights.size();
		}
		eid += act.expidx;
		Symbol leftS = exps[act.state].left;
		semanticAnalysis(eid,exps,symStack,table,leftS); // 还没有弹栈，进行分析，如果分析错误直接退出。
		for (int i = 0;i<expressLen;++i){
			symStack.pop();
			stateStack.pop();
		}
		symStack.push(leftS); //将左部压栈
		if(GOTO[stateStack.top()].find(exps[act.state].left)==GOTO[stateStack.top()].end()){
			cout<<sym.name<<" error2"<<endl;
			return -1;
		}
		// cout<<sym.name<<"-reduction"<<endl;
		// cout<<exps[act.state].left.name<<"->";
		// for (int i = 0;i<exps[act.state].rights[act.expidx].size();++i){
		// 	cout<<exps[act.state].rights[act.expidx][i].name<<" ";
		// }
		// cout<<endl;
		stateStack.push(GOTO[stateStack.top()][exps[act.state].left].state);
		return 1;
	}
}
/*
	@功能 读文件 获取所有token
	@参数 syms 引用类型 读到的放到这个变量里面
	@返回值 空
*/
void getSymbols(vector<Symbol> &syms){
	ifstream inf;
	inf.open("token.txt");
	string s;
	while(getline(inf,s)){
		Symbol sym;
		sym.type = 0;
		bool start = false;
		string s1,s2;
		for (int i = 0;i<s.size();++i){
			if (start){
				s2 += s[i];
			}
			else if (s[i]!=' '){
				s1 += s[i];
			}
			if (s[i]==' ') start = true;
		}
		if (s1=="id"||s1=="digits"){
			sym.name = s1;
			sym.attr.assignType.addr = s2;
		}
		else{
			sym.name = s2;
		}
		syms.push_back(sym);
	}
}

// 获取符号表
void getTable(vector<table_item> &table){
	ifstream inf;
	inf.open("SymbolTable.txt");
	table_item t;
	while(inf>>t.w_name>>t.w_kind>>t.w_type>>t.w_val>>t.w_addr){
		table.push_back(t);
	}
	inf.close();
}
void printStack(stack<Symbol> &symStack,string symName){
	stack<Symbol> tmp;
	const int size = symStack.size();
	string s = "$ ";
	for(int i = 0;i<size;++i){
		tmp.push(symStack.top());
		symStack.pop();
	}// 栈顶第一个 栈顶第二个 。。。
	for (int i = 0;i<size;++i){
		s += tmp.top().name+" ";
		symStack.push(tmp.top());
		tmp.pop();
	}
	cout<<s<<endl;
	// for (int i = 0;i<18-s.size();++i)
	// 	cout<<" ";
	cout<<"next:"<<symName<<endl<<endl;
}



int main(int argc, char const *argv[])
{
	ifstream inf;
	inf.open("grammar.txt");
	string s;
	vector<ProductionExpression> exps; // 所有的产生式子
	vector<table_item> table;// 符号表
	/*
		1.文法预处理
	*/
	ProductionExpression expStart;     // 增广文法
	vector<Symbol> rightStart;         //
	Symbol symStart;
	symStart.name = "P";               // 开始符号 增广文法
	symStart.type = 1;
	rightStart.push_back(symStart);
	expStart.rights.push_back(rightStart);
	expStart.left.name = "EE";
	expStart.left.type = 1;
	exps.push_back(expStart);

	while(getline(inf,s)){
		bool first = true; // 第一个字符为左部 标记一番
		int p1 = 0,p2 = 0; // 设置双指针找到子串
		int leftidx = -1;  // 产生式的下标
		vector<Symbol> expright;// 产生式右部
		for (int i = 0;i<s.size();++i){
			if (s[i]==' '){
				p2 = i;
				if (first){
					string left = s.substr(p1,p2-p1);
					if (!isupper(left[0])){
						cout<<"error : left is not upper symbol! failed"<<endl;
						exit(0);
					}
					// 找到一样的左部
					for(int j = 0; j < exps.size();++j){
						if (exps[j].left.name == left){
							leftidx = j;
							break;
						}
					}
					if (leftidx == -1){
						leftidx = exps.size();
						ProductionExpression exp;
						exp.left.name = left;
						exp.left.type = 1;
						exps.push_back(exp);
					}
					first = false;
				}
				else{
					Symbol sym;
					sym.name = s.substr(p1,p2-p1);
					sym.type = int(isupper(sym.name[0]));
					if (sym.name=="|"){
						exps[leftidx].rights.push_back(expright);
						expright.clear();
					}
					else{
						expright.push_back(sym);
					}
				}
				p1 = p2+1;
			}
			else if (i ==  s.size()-1){ // grammar.txt 产生式最后一个符号不为|
				p2 = i;
				Symbol sym;
				sym.name = s.substr(p1,p2-p1+1);
				sym.type = int(isupper(sym.name[0]));
				expright.push_back(sym);
				exps[leftidx].rights.push_back(expright);
			}
		}
	}
	inf.close();

	// 输出符合预期
	for(int i = 0;i<exps.size();++i){
		cout<<exps[i].left.name<<"->";
		for (int j = 0;j<exps[i].rights.size();++j){
			for (int k = 0;k<exps[i].rights[j].size();++k){
				cout<< exps[i].rights[j][k].name <<" ";
			}
			cout<<"|";
		}
		cout<<endl;
	}
	/*
		2. 求闭包 生成项集转化图
		需要用到前面计算结果 exps; // 所有的产生式子
		产生状态转换图 allItems
	*/
	kong.name = "@";
	kong.type = 0;
	vector<Items> allItems;// 集族

	// 最开始的一项
	Items items0;

	Item itemStart(0,0,0);
	items0.kernelItems.push_back(itemStart);

	closeure(exps,items0);  // 获取第1项的 非内核项
	items0.id = 0;          // 第一项的编号为0
	queue<Items> Qitems;    //所有项集
	Qitems.push(items0);
	allItems.push_back(items0);
	int count = 1;
	while(!Qitems.empty()){
		Items items = Qitems.front();
		Qitems.pop();
		vector<string> names;         // 所有的符号名字
		getAllNames(exps,items,names);// 获取第1项 所有点的下一项符号名字
		for (int i = 0;i<names.size();++i){
			if (names[i]=="@") continue;
			Items items2 = GoTo(exps,items,names[i]);
			bool flag = false;
			for (int j = 0; j<allItems.size();++j ){
				if (allItems[j]==items2){
					flag = true;
					allItems[items.id].directions.push_back(Direction(allItems[j].id,names[i]));
					break;
				}
			}
			if (!flag){
				closeure(exps,items2);
				items2.id = count++;  // 序号 也是allItems 下标
				Qitems.push(items2);
				allItems[items.id].directions.push_back(Direction(items2.id,names[i]));
				allItems.push_back(items2);
			}
		}
	}
/*
	3. 求出first集合和follow集合
*/
	unordered_map<Symbol,vector<Symbol>, myHashFuc > first;
	unordered_map<Symbol,vector<Symbol>, myHashFuc > follow;
	Symbol end;                        //初始化follow集
	end.name = "$";
	end.type = 0;
	follow[expStart.left].push_back(end); // 开始符号的follow集为"$"
	First(exps,first);
	Follow(exps,first,follow);
/*
	4. action表和goto表
*/
	unordered_map<int,unordered_map<Symbol,Act, myHashFuc> > ACTION;
	unordered_map<int,unordered_map<Symbol,Act, myHashFuc> > GOTO;
	action_goto(exps,allItems,follow,ACTION,GOTO); // 产生action表和goto表

/*
	5. 入栈处理和出栈处理
*/

	stack<Symbol> symStack;// 符号栈
	stack<int> stateStack; // 状态栈
	stateStack.push(0);    // 初始状

	vector<Symbol> syms;
	getSymbols(syms);   // 获取所有符号
	getTable(table);    // 获取符号表
	cout<<"########################"<<endl;
	for (int i = 0;i<syms.size();++i){
		printStack(symStack ,syms[i].name);
		while(Process(syms[i],exps,ACTION,GOTO,table,symStack,stateStack)==1){
				printStack(symStack ,syms[i].name);
		}
	}
	return 0;
}



